package fibonacci;

/**
 * 一、斐波那契数列模型
 * 4. 解码方法
 * 2024-10-18
 */
public class demo4 {
    public int numDecodings(String ss) {
        //1. 创建 dp 表（看返回值）
        int n = ss.length();
        int[] dp = new int[n];
        char[] s = ss.toCharArray();

        //2. 初始化
        //初始化 dp[0]
        if(dp[0] != '0') dp[0] = 1;
        if(n == 1) return 1;

        //初始化 dp[1]
        if(s[1] != '0' && s[0] != '0') dp[1] += 1;
        int t = (s[0] - '0') * 10 + (s[1] - '0');
        if(t >= 10 && t <= 26) dp[1] += 1;

        //3. 填表
        for (int i = 2; i < n; i++) {
            if(s[i] != '0') dp[i] += dp[i-1];

            int tt = (s[i-1] - '0') * 10 + (s[i] - '0');
            if(tt >= 10 && tt <=26) dp[i] += dp[i-2];
        }

        return dp[n-1];
    }


    /**
     * 虚拟节点，优化初始化
     * @param ss
     * @return
     */
    public int numDecodings2(String ss) {
        int n = ss.length();
        int[] dp = new int[n+1];
        char[] s = ss.toCharArray();

        dp[0] = 1;
        if(s[1-1] != '0') dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            if(s[i-1] != '0') dp[i] += dp[i-1];

            int tt = (s[i-2] - '0') * 10 + (s[i-1] - '0');
            if(tt >= 10 && tt <= 26) dp[i] += dp[i-2];
        }

        return dp[n];
    }
}
